package day230415;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/4/16 16:25
 * 年终奖
 */
public class Bonus {

    public int getMost(int[][] board) {
        int row = board.length;
        int col = board[0].length;
        // dp[i][j] 表示 i j 位置的最大价值
        // 状态转移方程: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + board[i-1][j-1](多申请空间后的offset有一个单位)
        int[][] dp = new int[row + 1][col + 1]; // 多申请空间, 避免边界问题
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + board[i-1][j-1];
            }
        }
        return dp[row][col];
    }
}
